package 数据结构.章节09;

/**
 * @author 挚爱之夕
 * @date 2021/10/12 - 10 - 12 - 18:08
 * @Description: 数据结构.章节09
 * @Version: 1.0
 */
public class _155_根据基准值分区单链表 {
    public static void main(String[] args) {
        int[] a = new int[]{6,5,4,3,2,1};
        int v = 3;
        Node head = new Node(a[0]);
        Node p = head;
        for (int i = 1; i < a.length; i++) {
            p.next = new Node(a[i]);
            p = p.next;
        }
        p = head;
        while(p != null){
            System.out.print(p.val + "\t");
            p = p.next;
        }
        System.out.println();
        p = process(head, 3);
        while(p != null){
            System.out.print(p.val + "\t");
            p = p.next;
        }
    }
    private static class Node{
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    private static Node process(Node head, int val){
        Node p = head;
        //将链表分两部分
        Node leftHead = null;
        Node leftTail = null;
        Node rightHead = null;
        Node rightTail = null;
        while(p != null){
            int value = p.val;
            if(value >= val){
                if(rightHead == null){
                    rightHead = p;
                    rightTail = p;
                } else {
                  rightTail.next = p;
                  rightTail = rightTail.next;
                }
            }else{
                if(leftHead == null){
                    leftHead = p;
                    leftTail = p;
                }else{
                    leftTail.next = p;
                    leftTail = leftTail.next;
                }
            }
            p = p.next;
        }
        if(leftHead == null)
            return rightHead;
        //将尾next赋值为null,不然可能是环状链表
        if(rightTail != null){
            rightTail.next = null;
        }
        leftTail.next = rightHead;
        return leftHead;
    }
}
